//
// Created by Administrator on 2024/10/26.
// 埃氏筛法
//

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 100; //25
    n = 1000;//168
    n = 10000;//1229
    n = 100000;//9592
    bool isp[n + 1] = {0};
    for (int i = 2; i <= n; ++i)
        isp[i] = 1;
    for (int i = 2; i*i <= n; ++i)
    {
        if (isp[i])
        {
            for (int j = i+i; j <= n ; j+=i)
            {
                isp[j]=0;
            }
        }
    }
    int count=0;
    for (int i = 0; i <=n ; ++i)
    {
        if(isp[i])
            count++;
    }
    cout<<count;
    return 0;
}